package leetcode.editor.cn.dsa11_sort;
// 特殊的二进制序列是具有以下两个性质的二进制序列：
// 0 的数量与 1 的数量相等。
// 二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。 
// 
// 给定一个特殊的二进制序列 S，以字符串形式表示。定义一个操作 为首先选择 S 的两个连续且非空的特殊的子串，然后将它们交换。（两个子串为连续的当且仅当第一
//个子串的最后一个字符恰好为第二个子串的第一个字符的前一个字符。) 
//
// 在任意次数的操作之后，交换后的字符串按照字典序排列的最大的结果是什么？ 
//
// 示例 1: 
// 输入: S = "11011000"
// 输出: "11100100"
// 解释:
// 将子串 "10" （在S[1]出现） 和 "1100" （在S[3]出现）进行交换。
// 这是在进行若干次操作后按字典序排列最大的结果。
// 
// 说明:
// S 的长度不超过 50。
// S 保证为一个满足上述定义的特殊 的二进制序列。 
// 
// Related Topics 递归 字符串 
// 👍 55 👎 0

public class SpecialBinaryString761 {
    public static void main(String[] args) {
        Solution solution = new SpecialBinaryString761().new Solution();
        System.out.println(solution.makeLargestSpecial("11011000"));
        //11100100
        System.out.println(solution.makeLargestSpecial("1110110000"));
        //1111001000
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String makeLargestSpecial(String S) {
            // 1.结束条件
            // 2.函数主功能：遍历查找子串、子串排序、子串逆序拼接成字符串
            // 3.等价关系式：在子串排序前，先递归处理子串 f(n)=S(f(n1),f(n2),f(n3)...)
            if (S.length() <= 2) {
                return S;
            }
            // 1.找出满足要求的特殊子串
            // 存储连续的特殊子串，符合要求的字符串必定是1开头0结尾的
            String[] arr = new String[25];
            int index = 0;
            int countOne = 0; // 存放1、0的数量差
            int start = 0; // 符合规则特殊子串的起始位置
            int len = S.length();
            // 从前往后遍历查找，以start开头是否存在符合要求子串
            for (int i = 0; i < len; i++) {
                countOne += S.charAt(i) == '1' ? 1 : -1; // 计算1、0的数量差
                if (countOne == 0) { // 表示找到一个特殊子串
                    // 对特殊字串去掉头尾1、0然后递归求解字典序最大
                    String result = makeLargestSpecial(S.substring(start + 1, i));
                    // 在递归结果上添加头尾1、0放入到字符串数组中
                    arr[index++] = "1" + result + "0";
                    // 记录特殊子串下标位置
                    start = i + 1;
                }
            }

            // 2.对数组中的连续子串进行冒泡排序
            sort(arr, index);
            StringBuilder sb = new StringBuilder();
            // 3.排序后的连续子串，逆序（字典序最大）拼接成字符串
            for (int i = index - 1; i >= 0; i--) {
                sb.append(arr[i]);
            }
            return sb.toString(); // 返回排序后的字符串
        }

        // 冒泡排序
        public void sort(String[] arr, int length) {
            for (int i = 0; i < length; i++) {
                for (int j = 0; j < length - 1 - i; j++) {
                    if (arr[j].compareTo(arr[j+1]) > 0) {
                        String temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                    }
                }
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}